package com.exam.pinduoduo;

import java.util.Scanner;

/**
 * date:
 * description:
 */
public class Solution002 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = Integer.parseInt(scanner.nextLine().trim());
        for (int i = 0; i < count; i++) {
            String line = scanner.nextLine();
            String[] strs = line.trim().split(" ");
            int K = Integer.parseInt(strs[0]);
            int len = Integer.parseInt(strs[1]);
            String str = scanner.nextLine();
            if(K == 0 || len == 1){
                System.out.println(1);
                continue;
            }
            if(isPalindrome(str)){
                System.out.println(1);
            }else{
                System.out.println(2);
            }
        }
    }

    public static boolean isPalindrome(String str){
        int l = 0, r = str.length() - 1;
        while(l < r && str.charAt(l) == str.charAt(r)){
            l++;
            r--;
        }
        if(l >= r){
            return true;
        }else{
            return false;
        }
    }
}
